package leetcode.editor.vscdev.hot100;

import java.util.*;

import leetcode.editor.utils.*;

public class lc102 {

}

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        return func1(root);
    }

    private List<List<Integer>> func1(TreeNode root) {
        // 队列模拟迭代
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> res = new ArrayList<>();
        // 遍历队列获取子层级节点, 队列中存放未遍历的节点
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 队列未空, 说明没有需要遍历的节点了才终止
            int size = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                /*if (node == null){
                    // 这样处理打印null节点
                    temp.add(null);
                    continue;
                }
                temp.add(node.val);
                queue.add(node.left);
                queue.add(node.right); */
                temp.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
    private List<List<Integer>> func2(TreeNode root){
        // 递归dfs
        if(root==null) {
			return new ArrayList<List<Integer>>();
		}
		//用来存放最终结果
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		dfs(1,root,res);
		return res;
    }
    private void dfs(int index,TreeNode root, List<List<Integer>> res){
        //假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
		if(res.size()<index) {
			res.add(new ArrayList<Integer>());
		}
		//将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
		//res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
		res.get(index-1).add(root.val);
		//递归的处理左子树，右子树，同时将层数index+1
		if(root.left!=null) {
			dfs(index+1, root.left, res);
		}
		if(root.right!=null) {
			dfs(index+1, root.right, res);
		}
    }
}
